Giga Games 1/Giga Games.iso/net/go/comp/hp_xgo.inf

Internet Message Format | 1993-06-20 | 20.9 KB

Path: milton!uw-beaver!ubc-cs!alberta!aunro!ukma!asuvax!cs.utexas.edu!sdd.hp.com!hplabs!hpcc05!hpcuhb!hpihoah!fotland
From: [e-mail] (David Fotland)
Newsgroups: rec.games.go
Subject: X11 Go program available (includes two player mode)
Message-ID: <[e-mail]>
Date: 26 Nov 91 19:38:16 GMT
Organization: Hewlett Packard, Cupertino
Lines: 482


Announcing the release of xgo, an X11 port of "Many Faces of Go" for Hewlett
Packard computers.  This version is somewhat stronger than the IBM-PC version,
and emulates the IBM VGA graphic display.  It includes a two screen, two
player mode for person to person games over a network.

This version is free, and you can get it via anonymous ftp from uunet.uu.net
as games/HP-xgo.shar.Z.  Use binary more to transfer it, then uncompress and
sh to get the individual files.  See the README file for installation
instructions.  This file is about 2.75 Mbytes, and uncompresses to about 6
Mbytes.

Note that this shar contains binaries only, no source code, and contains
binaries that will run on any Hewlett-Packard HP9000 computer, either 680x0
based or HP-PA Risc based.

David Fotland (3 Dan)

PS - here is some more description of the various versions of my Go program:


Documentation for "The Many Faces of Go", Cosmos, IGO, and xgo,
a program that plays Go, by David Fotland. (11/26/91)

"The Many Faces of Go" is a GO program for the IBM-PC that includes
an extensive tutorial on the rules and strategy, a set of introductory
problems (from Graded Go Problems For Beginners), several professional games
with commentary (and the ability to present additional games available
from Ishi Press), a Joseki tutor with about 15,000 moves, and one of the
strongest Go playing computer opponents available.  MFGO was introduced
in January, 1991, and currently holds the title of "North American Computer
Go Champion".

Cosmos was the previous version of this program, introduced in September,
1988, and is no longer available, since MFGO is a stronger player and has
a much better user interface.

IGO is a 9 line only introductory version of Many Faces of Go for the IBM-PC
that is available from the American Go Association or Ishi Press.  It is
free (except for shipping and handling), and may be freely copied and given
away to friends.

Xgo is a port of Many Faces of Go to X11 release 4 on the Hewlett Packard
HP9000  3xx, 4xx, 6xx, 7xx, and 8xx computers.  It emulates the VGA graphics
interface from MFGO, and has a two player, two screen mode for playing games
with friends over the net.

The most recent Cosmos is Rev 6.11.  The most recent Many Faces of Go is
Rev 7.03.  The most recent xgo is Rev 7.34.  The most recent rev of IGO is
7.5.  All programs share the same source code.

MFGO plays the oriental game of Go, a 2 player board game where the object
is to surround territory.  Players take turns putting pieces (called stones)
on a board.  Once played a piece does not move, although it may be captured.
Play continues until both players pass and the score is the number of points
surrounded plus the number of prisoners.  Highest score wins.

Tournament Results:

"Best Design" award 1991 World Computer Go Championship
1st place 1991 North American Computer Go Championship
10th place 1991 World Computer Go Congress
5th Place 1990 USA Computer Go Championship
2nd place 1989 USA 19 line computer Go championship
7th place 1989 World 19 line computer Go championship
1st place 1988 Usenix 19 line computer Go tournament
1st place 1988 USA 19 line Computer Go championship
8th place 1988 World 19 line computer Go championship
2nd place 1988 World 9 line Computer Go championship
4th place 1987 World 19 line computer Go championship
4th place 1987 World 9 line Computer Go championship

MFGO is about 15 Kyu strength.  Xgo is about 13 Kyu strength.  Beginners are
about 25 to 30 kyu.  Smaller numbers are stronger players.  The difference in
rank is the number of handicap stones given on a 19 line board.  Most serious
players get to 6 to 10 kyu within a year or two if they have stronger people
to play.  After one kyu, the next rank is one dan and ranks go up to 9 dan
with the strongest amateur players at 7 or 8 dan.  My rank is 3 Dan.

How to get it:

If you are inside HP, xgo is ninstallable from hpihoah.  The package is
called "go" and includes a man page.  It puts "xgo" in /usr/local/games,
the man page "xgo.6" in /usr/local/man/man6, and the data files and graphic
bitmaps in /usr/local/games/lib/xgo.  It also installs an old X10 and curses
version as /usr/local/games/go.

From outside HP you can get Xgo from uunet.uu.net via anonymous FTP.
Look in games/hp-xgo.shar.Z.  This shar file contains binary executables
for both HP9000 68000 based machines (3xx and 4xx) and RISC based machines
(6xx, 7xx, 8xx), as well as documentation and data files.  The file is about
2.75 Mbytes, and uncompresses to about 6 Mbytes.  Transfer it in binary mode,
then use 'uncompress hp-xgo.shar.Z' to uncompress it, then 'sh hp-xgo.shar'
to split out the separate files.

Xgo is available free on Hewlett Packard 9000 series computers.  MFGO is
available for IBM PC or compatibles with at least 512 Kb of memory as
"The Many Faces of Go", for $59.95 (plus $3.00 postage and handling)
in many computer and game stores or from:

Ishi Press
76 Bonaventura Dr.
San Jose CA 95134
[phone]

I do not distribute source since this is one of the stronger programs in
the world and I want to win the world championship.  I have no plans to port
this program to any other Unix based machines, especially not
to Sun workstations.  I may port it to the Macintosh, Amiga, or
NeXt machines.


Usage (for Xgo  X11 version):

xgo [-sSIZE] [-lLEVEL] [-hHANDICAP]  [-display FOO:0.0] [-display2 BAR:0.0]

SIZE is size of board (7 to 19).  Default is 19.
LEVEL is the playing level (0-20).  Default is 10
HANDICAP is number of handicap stones
-display FOO:0.0 use FOO for display
-display2 BAR:0.0  use BAR for the second player


MFGO and xgo have a setup screen that allows setting of playing level,
handicap, rules, color played, and some user interface parameters.

The playing level controls the number of nodes visited in each tactical
search and the number of moves considered on the full board.  Higher numbers
are slower, but allow the program to read out more difficult tactical
situations and find less obvious moves.  MFGO/Xgo has 20 playing levels,
which cover the same range as the 100 playing levels in Cosmos.

MFGO/Xgo allows black to start with handicap stones on the board to make up for
a difference in strength between the players.

Japanese rules are commonly used in the US and Japan.  The Ing Chinese rules
are used in Taiwan and are the official rules of the Ing computer Go
championship (the one with the $1.5 Million prize).

Many Faces of Go Info:

MFGO will run on any IBM PC, XT, AT, PS/2 system, Tandy 1000, or clone.  The
machine  should have at least 512Kb of RAM (Cosmos is about 450K) and a 5 1/4
inch or 3 1/2 inch floppy drive.  MFGO is distributed on two 362Kb floppy
disks and one 3 1/2 inch disk.  It is not copy protected.  To run it, just
type go.  It allows you to set up a configuration for the game where you can
specify board size, handicap, computer to play black, white, both or neither,
beep for Atari, playing level, archive all games to disk, randomize moves (so
it doesn't always play the same game), etc.  You can save the configuration on
 the disk.

MFGO supports  Hercules, CGA, EGA, VGA (Color or Mono), Tandy, and Laptop
graphics modes.  In each mode it uses the highest resolution available and has
shaded stones.  In VGA the board has a realistic wood grain.  The VGA graphics
are use for the X11 version.

The rules and strategy of Go are on line and there is extensive on line help
for the configurations, playing, and scoring, including a 90 screen on line
tutorial presented in question/answer format (using the text from the AGA
book "The Way to Go") with two commented small board games.

Games can be saved and restored, or reviewed move by move.

MFGO can explain its reasons for picking a move and can give you a hint
as to where you should move next (and explain the reasons for the hint).

MFGO includes a joseki tutor that allows you to browse the 15,000 move joseki
library.

MFGO is designed to be very easy to use for the Go and or computer novice and
is a good way to introduce someone new to Go.  It can play games on small
boards.  It supports any odd size from 9x9 to 19x19.

Igo information:

Igo is MFGO restricted to a 9 line board, and it includes a new, improved
on line tutorial presented in problem/answer format (using the text from the
AGA book "The Way to Go").  Igo has 4 levels, which control the playing
strength and the handicap, so an improving player will move up in levels.
Igo is intended primarily to introduce new players to the game.


How it Works:

Go is a very difficult problem.  There is no single idea that can generate
strong moves (like searching in chess).  Strong programs are strong
because they have lots of go knowledge.  The most important thing is a
way to organize lots of go knowledge so it can be used quickly.  MFGO
has 250 major move suggesting rules (and most of them are results of
several subrules).  It has a 26,000 move annotated joseki library.  It has
320 patterns in a pattern library. It has maybe 50 rules each hardcoded into
the tactical analyzer, connection evaluator, eye evaluator, and life and
death evaluator.  It has 3 different territory evaluators which are used
in different circumstances.  (One for secure eye space, one for liberties,
and one for influence.)

The move suggesting rules suggest moves to try and probable values.  These are
sorted and the "playing level" top moves are further considered.  Each of
these moves are made on the board and the position evaluated and scored
(using the tactical analyzer, eye evaluator, etc.)  The move which leads
to the best score is played.

Details

There are three parts of a Go program; the data structures for representing
go knowledge, the evaluation function for determining the score, and
the move selection expert system.

Data structures:

My most basic data structure is a sorted list of integers.  I use it for things
like lists of liberties, lists of neighboring groups, and lists of eyepoints.
I keep track of local structures like liberty lists incrementally.  Some
global structures like the amount of influence on each square are completely
recalculated every move.  For some things like the value of an eye I only
recalculate ones that change.  Most data structures are attached to strings
or groups rather than squares on the board.

Important data structures:

Per point (intersection):
    Color (black, white, or empty)
    String number
    Number of adjacent black, white, empty points
    List of adjacent empty points
    White and black influence
    Which eye is this point part of
    List of connections through this point
    List of patterns that match here

Per string (set of adjacent stones of same color, unit of capture):
    Number of liberties
    List of liberties
    List of adjacent enemy strings
    Group number
    List of connections from this string
    Aliveness
    Tactically threatened flag

Per Group (set of unbreakably connected strings):
    List of component strings
    Aliveness
    Number of liberties
    List of liberties
    List of eyes
    Number of eyes
    List of eye potentials
    List of running points

Per connection:
    Two string numbers
    Status of connection (unbreakable, cuttable, etc)
    Type of connection (hane, knights, one point jump, etc)
    List of points in connection

Per eye:
    List of points in eye
    How many eyes if I move first
    How many eyes if enemy moves first
    How many eyes if enemy gets two moves in a row
    List of vital points
    Type of eye (one_point, dead_group, line, etc.)

Per eye potential
    Type of potential (eye vital point, extend, connect, etc)
    Amount of potential

Per running point
    Type of point (toward friend, toward enemy, etc)

Evaluating a position:

First, figure out where the strings of stones, liberties, liberties
of liberties, stones next to empty squares, and connections are (I do this
incrementally).  A string of stones is the unit of capture in Go.

For each string, see if it is tactically captured if it moves first.  If so,
mark it DEAD.

For each string, see if it is tactically captured if it moves second.  If so,
mark it THREATENED.

Find all of the connections between strings.  Check tactically if they are
cuttable or not.  (Knowing which strings are DEAD or THREATENED is a big
help here.)

Collect all of the strings that are unbreakably connected into groups.

Analyze all the eyes on the board and assign them to groups.  An eye
is a small space mostly surrounded by stones or a small DEAD group.  MFGO
knows the dead shapes and vital points.  It checks the diagonals of small eyes
to see if they are false.  Figure out the value and potential of each eye.
(For example, 3 in a row has a value of one eye and potential of two eyes).

Find all of the territory completely controlled by each group which was not
already counted as eyes.  This is the army's EYESPACE.

For each group, if it has eyes plus EYESPACE for two eyes, mark it ALIVE.

Radiate influence from the ALIVE groups (and negative influence from DEAD
ones), and slight influence from the other stones.

For each group that is not ALIVE or DEAD, figure out how strong it is.  Take
into account potential connections, potential extensions along the edge,
potential eyes.  If it has two independent moves that could make two eyes,
mark it MIAI-ALIVE.  If it has one move that can make it alive, mark it
UNSETTLED.

The remaining groups are WEAK.  Look for two adjacent WEAK groups to find
semeais and sekis.  See if the radiated influence from a friendly live group
hits a weak group.  If so it is not surrounded.  Separate the WEAK groups
that can run or fight from the ones that are hopeless.  Generally a WEAK
group that can't run and has ALIVE neighbors and few liberties is hopeless.

Each point with a stone on it or adjacent to a stone or between a stone
and the edge is scored according to how alive the stone is.  Other points
are scored based on the radiated influence.

Unsettled groups are scored differently depending on who has the move.

The guts of the evaluation function is based almost entirely on life and
death considerations.  My feeling is that you can make 20 kyu moves based on
shape alone, but you can't get to 10 kyu unless you can tell which groups
are strong and which are weak, and especially which are unsettled.

MFGO classifies groups according by how strong they are into the following
classes:

        HERE DOWN ARE DEAD
        25 - tactically captured unconditionally
        24 - presumed dead because surrounded without
           any eyes (smothered small group)
        23 - Temp used for weak groups undecided yet
        22 - No eyespace or potential and nbrs all alive
        21 - probably dead.  some eye space or potential, nbrs alive
        20 - in semeai loses
        HERE DOWN ARE WEAK - PROBABLY WILL DIE
        19 - no running ability, weak nbrs and some eye potential
        18 - can't run, lots of eye potential, only one eye
             has aji to live, or can be used as ko threats
                17 - in a semeai. behind - aji for later
        16 - poor running ability - can't live in one move
        HERE DOWN ARE UNSETTLED
                15 - in a semeai. unsettled
        14 - Running fight (can run and there are adjacent weak groups)
        13 - surrounded, can live or die in one move
        13 - would be alive, but tactically threatened
                12 - in a semeai. Ahead or temporary seki
        11 - unsettled - can live in one move or limp away
        HERE DOWN ARE ALIVE (or settled for now)
        10 - can run away easily, no eyes
        9 - can run away easily, one eye
            needs two moves to make second eye
        8 - can live in one move or run easily
                7 - Alive because wins semeai
                6 - alive in seki
                5 - miai for barely space for two eyes (dangerous)
        4 - barely territory for two eyes (dangerous)
        HERE DOWN ARE VERY ALIVE
                3 - miai for lots of eye space - 3 or more ways to make
                    second eye
        2 - absolutely unconditionally alive - two small eyes
            or lots of territory

The influence function:

Once we know the strength of groups we can radiate influence to determine
where the territory is.  Influence is radiated independently from each
stone and summed at each point.  The influence function falls off as
1/distance, and does not go through stones or connections.  A function
that falls off as 1/distance will create a constant field inside
any fully enclosed area, no matter how big it is, which is what we want
for territory.  Dead stones radiate negative influence.

The tactician:

The tactician does a single tactical search with the goal of capturing a
string.  It gets passed the maximum liberty count, maximum depth, and maximum
size of the search.  When seeing if strings are DEAD or THREATENED the
maximum liberty count is 4.  If a string gets 5 liberties it is assumed to
escape.  The maximum depth is about 100 which allows a ladder across the
board to be read out.  The size of the search is the playing level, which
controls the number of decisions made.  Forcing moves don't count, so a ladder
can be read out even at low levels.  Eye and connection evaluations use
much smaller values for the size of the search since for a solid eye or
unbreakable connection you want to capture quickly.  The tactician does about
200 nodes per second per MIP.

Move Selection:

I used to just try every move and score the board.  This worked OK, but was
very slow.  Now I have a bunch of move suggestion code organized as a set
of experts which suggest moves along with the reason for making them.
There are over 250
reasons for making a move.  Each reason comes with a bonus value, a guess
value, a minimum aliveness, and an indication of which group is being
attacked or defended (if any one is).  The moves are sorted by the guess value
and some number of them are tried (controlled by the playing level).  After
a move is tried we check if the rule applied.  For example, if the rule
is "Make an eye to save an unsettled group" and after the move is made the
group is still unsettled, then the rule did not work and the move is
rejected.  If the move is an attacking move, the attacked group must end up
weaker.  If the move is a defending move, the defended group must end up
stronger.  If the rule applied, we check to see if the move is sente, and
add a bonus if it is.  The position is evaluated (as described above) and
the rule bonus and sente bonus are added.  If there is a move tree associated
with this move (from a joseki or a pattern match) the moves in the tree
are placed on the board and evaluated (as above), then the scores are
backed up using minimax.  After trying each move, the one
which led to the highest score (counting bonuses) is made.  In evaluating
the position a local quiescence search is made.

Move Suggestion:

The move suggestion experts are:

Fuseki
    Playing in empty corner
    Shimari and kakari
    Joseki moves
Big moves on edge
    Towards enemy
    Invasions
    Between friendly stones
Playing in the center (reducing moves and junction lines)
Playing safe when ahead
    Respond when enemy adds stone to dead group
Squirming around when behind
    Make a bogus invasion
    try to make a hopeless group live
Pattern matching
    patterns for cutting and connecting
    patterns for surrounding and avoiding getting surrounded
    endgame patterns
    killing/saving groups patterns
    Shape moves
Saving a weak group
    making eyes
    running
    fighting semeais
Save threatened string
Capture threatened string
Killing a weak group
    surrounding
    taking eyes
Cutting and connecting
Contact fights
    Blocking
    extending for liberties
    hane
Ko threats
    make a big atari
Filling dame

There is a Joseki library which can suggest joseki moves.  It's
organized as an directed acyclic graph (not a tree).  Moves are marked as
normal, urgent, bad (these moves are ignored
but the response is in the library in case the opponent makes one), followup,
etc.  The Joseki database is encoded in about 1.2 bytes per move.

There is a pattern matcher with over 300 patterns in it.  Each pattern is
8x8, where each point is specified as black, white, empty, don't care,
white or empty, black or empty, or black or white.  Each pattern has
a set of attributes with it that must also match.  For example, the
stone at (4,2) must be alive, or the stone at (2,5) must have at least
2 liberties.  Each pattern has a move tree attached that is used for
full board lookahead.  There are about 1600 moves in all the move trees.

The move suggestion code is easily extensible by adding more patterns or
firing rules based on other criteria.  The program has text associated with
each rule so it can "explain" its reasons for making moves.  This makes it
easy to debug.

Program Size:

Many Faces of Go is about 41,000 lines of code with about 15,000 of those
lines in the user interface and the rest in the playing algorithm.  It is
written entirely in C except for a small amount of PC video graphic interface
code which is in 80x86 assembler.  On the PC, MFGO occupies about 440 Kbytes
in memory, about 2/3 code and 1/3 data.

-David Fotland